package org.pupil.stack;

import java.util.Stack;

/**
 * @Description: 最小栈     leetcode：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof
 * 核心：
 * 1. 设置一个数据栈(data)和一个最小值栈(min)，两个栈同步更新
 * 2. 当入栈 min为空或者x <= min顶，min压入x
 * 3. 当入栈 x > min顶，min压入min顶
 * 4. data出栈时，min同步出栈
 * @Author: pupil
 * @Date: 2024/08/04 下午 3:11
 */
public class MinStack {

    private Stack<Integer> data;
    private Stack<Integer> min;

    public MinStack() {
        data = new Stack<>();
        min = new Stack<>();
    }

    public void push(int x) {
        data.push(x);
        if (min.isEmpty() || x <= min.peek()) {
            // 当入栈 min为空或者x <= min顶，min压入x
            min.push(x);
        } else {
            // 当入栈 x > min顶，min压入min顶
            min.push(min.peek());
        }
    }

    public void pop() {
        data.pop();
        min.pop();
    }

    public int top() {
        return data.peek();
    }

    public int getMin() {
        return min.peek();
    }

}

/**
 * 优化性能，使用数组实现栈
 * leetcode的数据在测试时，同时在栈里的数据不超过这个值
 * 如果leetcode补测试数据了，超过这个量导致出错，就调大
 */
class MinStack2 {
    private final int MAXN = 8001;

    private int[] data;
    private int[] min;
    int size; // 栈长度

    public MinStack2() {
        data = new int[MAXN];
        min = new int[MAXN];
        size = 0;
    }

    public void push(int x) {
        data[size] = x;
        if (size == 0 || x <= min[size - 1]) {
            min[size] = x;
        } else {
            min[size] = min[size - 1];
        }
        size++;
    }

    public void pop() {
        size--;
    }

    public int top() {
        return data[size - 1];
    }

    public int getMin() {
        return min[size - 1];
    }
}
